﻿//1.leetcode  146.LRU缓存

//首先我们要知道LRU表示最近最少使用以及LRU内存空间是有限的
//我们需要将内存中的所有元素按照使用的顺序进行排序
//因为当内存空间满了的话,当我们需要插入新元素时,我们需要将最后一个操作过的元素进行删除,再插入新元素(LRU的特点)
//因此我们需要对内存中元素操作过的顺序进行一定的排
//具体思路:使用左右两个指针来维护LRU的内存空间块,将每次操作的新元素转移到内存块的最左边,
//这样就会使得最后操作过的元素在内存块的最右边(空间满后要插入新元素的话直接利用右指针删除最右边的元素即可)
//根据上面的介绍:我们可以使用双链表与哈希表来维护LRU缓存机制


//哈希表的两个重要函数的使用(不要搞混了):
//mapped_type& operator[](key_type&& k): 如果key在容器中匹配,则返回value的引用。如果未找到key,则将其插入容器
//size_type count(const key_type& k): 由于unordered_map不允许存储具有重复key的元素(所以其返回值是0或1),
//                                    所以count()函数本质上是检查unordered_map中是否存在具有给定key的元素

class LRUCache {
public:
    struct Node //双链表的节点
    {
        int key, val;
        Node* left, * right;
        Node(int _key, int _val) :key(_key), val(_val), left(nullptr), right(nullptr)
        {}
    }*L, * R;

    //使用哈希表与双链表进行维护(<key,value>  --->   <int,Node*>)
    unordered_map<int, Node*> hash;
    int n;

    //初始化LRU缓存,使用左右两个虚拟指针来维护该段空间     
    LRUCache(int capacity)
    {
        n = capacity;
        L = new Node(-1, -1);
        R = new Node(-1, -1);
        L->right = R;
        R->left = L;
    }

    //移除双链表的某个节点
    void Remove(Node* p)
    {
        p->left->right = p->right;
        p->right->left = p->left;
    }

    //将移除的p节点转移到列首
    void Insert(Node* p)
    {
        p->right = L->right;
        L->right->left = p;
        p->left = L;
        L->right = p;
    }

    //由key获取LRU内部value节点的数据val值:
    //(1)key不存在就返回-1;
    //(2)key存在就返回key对应的value节点的val值(key对应的value此时是最新操作节点,所以需要将其置为首节点)
    int get(int key)
    {
        if (!hash.count(key)) return -1;
        Node* p = hash[key];
        Remove(p);
        Insert(p);
        return p->val;
    }

    //如果关键字key已经存在,则变更其value节点的val值;如果不存在,则向LRU内存块中插入该组 <key,value>
    //如果插入操作导致关键字数量超过capacity,则应该逐出最久未使用的关键字。
    void put(int key, int value)
    {
        if (hash.count(key)) //key已经存在
        {
            Node* p = hash[key];
            p->val = value;
            //操作过就变成了最新操作的节点,需要改变其位置
            Remove(p);
            Insert(p);
        }
        else  //key不存在
        {
            if (hash.size() == n) //空间已满,移除最后操作的节点
            {
                Node* p = R->left;
                Remove(p);
                hash.erase(p->key); //将哈希表中维护的该节点删除(要注意erase使用时所需的参数)
                delete p;
            }
            Node* p = new Node(key, value);
            hash[key] = p; //哈希表维护节点!!!(新节点需要并入哈希表中)
            Insert(p);
        }
    }
};